#include <stdio.h>
#include <stdlib.h>
enum node_color
{
    red,
    black
};
typedef struct tree
{
    int key;
    struct tree *left, *right, *parent;
    node_color color;
};
tree *n = (tree *)malloc(sizeof(tree));
tree *insert_tree(tree *&root, int key)
{
    if (root == n)
    {
        root = (tree *)malloc(sizeof(tree));
        root->key = key;
        root->color = red;
        root->left = root->right = n;
        root->parent = n;
        return root;
    }
    else
    {
        tree *child;
        if (root->key > key)
        {
            child = insert_tree(root->left, key);
        }
        else if (root->key < key)
        {
            child = insert_tree(root->right, key);
        }
        else
            return root;
        if (child->parent == n)
            child->parent = root;
        return child;
    }
}
tree *left_rotation(tree *&A)
{
}
tree *right_rotation(tree *&A)
{
}
void RB_insert(tree *&root, int key)
{
    tree *p = insert_tree(root, key);
    while (p != root && p->parent->color == red)
    {
        tree *g = p->parent->parent;
        if (p->parent == g->left)
        {
            tree *t = g->right;
            if (t->color == red)
            {
                g->color = red;
                t->color = p->parent->color = black;
                p = g;
            }
            else
            {
                // case 2 转化成 case 3
                if (p == p->parent->right)
                {
                    p = left_rotation(p->parent);
                }

                // recolor

                right_rotation(p->parent);
            }
        }

        else
        {
            tree *t = g->left;
            if (t->color == red)
            {
                g->color = red;
                t->color = p->parent->color = black;
                p = g;
            }
            else
            {
                if (p == p->parent->left)
                {
                    right_rotation(p->parent);
                }
                // recolor
                left_rotation(p->parent);
            }
        }
    }
    root->color = black;
}
int main()
{
    /*******************code*******************/
    n->color = black;
    n->left = n->right = n->parent = NULL;
    n->key = 0;

    tree *root = n;
    tree *p;
    int a[] = {10, 3, 7, 18, 9, 5, 11};
    for (int i = 0; i < 7; i++)
    {
        RB_insert(root, a[i]);
    }
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
